#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define RED 0//红色
#define BLACK 1//黑色

// 整个红黑树 插入操作 结构
//————————————————————
//红黑树节点结构
typedef struct RBTreeNode
{
	int data;//数据2
	struct RBTreeNode* l;
	struct RBTreeNode* r;
	struct RBTreeNode* parent;//双亲节点
	int color;//0红1黑，宏定义
}RBTNode,*RBTree;
//创建红黑树节点
RBTNode* createNode(int key, RBTNode* parent, RBTNode* left, RBTNode* right)
{
	RBTNode* s = (RBTNode*)malloc(sizeof(RBTNode));
	s->data = key;
	s->parent = parent;
	s->l = left;
	s->r = right;
	s->color = RED;//初始节点颜色设置为红色
	return s;
}
//左旋：以红黑树的x节点为中心左旋(RR)
RBTree left_rotation(RBTree root, RBTNode* x)
{
	//0、y指向x的右孩子
	RBTNode* y = x->r;
	//1、y的左孩子变成x的右孩子
	x->r = y->l;
		//处理y->L的父亲关系
	if (y->l != NULL)
	{
		y->l->parent = x;
	}
	//2、y调到x的位置
		//处理y的父子关系
	y->parent = x->parent;
		//处理位置关系
	if (x->parent == NULL)
	{//旋转点是根节点
		root = y;
	}
	else
	{
		if (x == x->parent->l)
			x->parent->l = y;
		else
			x->parent->r = y;
	}
	//3、x变成y的左孩子
	y->l = x;
		//处理父子关系
	x->parent = y;
	return root;
}
//右旋：以红黑树的x节点为中心右旋(LL)
RBTree right_rotation(RBTree root, RBTNode* x)
{
	//0、y指向x的左孩子
	RBTNode* y = x->l;
	//1、y的右孩子变成x的左孩子
	x->l = y->r;
		//处理y->R的父亲关系
	if (y->l != NULL)
	{
		y->l->parent = x;
	}
	//2、y调到x的位置
		//处理y的父子关系
	y->parent = x->parent;
	//处理位置关系
	if (x->parent == NULL)
	{//旋转点是根节点
		root = y;
	}
	else
	{
		if (x == x->parent->l)
			x->parent->l = y;
		else
			x->parent->r = y;
	}
	//3、x变成y的右孩子
	y->r = x;
	//处理父子关系
	x->parent = y;
	return root;
}
//调整（一、父亲在右：1.叔叔为红 【染色】，2.叔叔为黑 【染色】+【旋转】；
//		二、父亲在左：1.叔叔为红 【染色】，2.叔叔为黑 【染色】+【旋转】。）
RBTree fixUp(RBTree root, RBTNode* z)
{
	RBTNode* p = z->parent;//z的父亲
	RBTNode* g = NULL;//z的爷爷
	RBTNode* u = NULL;//z的叔叔

	while (p != NULL && p->color == RED)
	{
		//调整
		g = p->parent;
		if (p == g->r)
		{//一）父亲在右
			u = g->l;//叔叔可能是空的
			if (u != NULL && u->color == RED)
			{//1.叔叔为红【染色】
				u->color = BLACK;
				p->color = BLACK;
				g->color = RED;
				z = g;//爷爷节点重新变成新的调整节点
				p = z->parent;
			}
			else
			{//2.叔叔为黑：【染色】+【旋转】
				//先写RL后写RR是因为，如果满足RL的条件就能够先直接变成RR再进行RR，不满足就直接进行RR
				//RL
				if (z == p->l)
				{
				//【染色】
					root = right_rotation(root, p);
					RBTNode* t = z;
					z = p;
					p = z;
				}
				//RR
				//【染色】
				p->color = BLACK;
				g->color = RED;
				//【旋转】
				root = left_rotation(root,g);
			}
		}
		else
		{//一）父亲在左
			u = g->r;//叔叔可能是空的
			if (u != NULL && u->color == RED)
			{//1.叔叔为红：【染色】
				u->color = BLACK;
				p->color = BLACK;
				g->color = RED;
				z = g;//爷爷节点重新变成新的调整节点
				p = z->parent;
			}
			else
			{//2.叔叔为黑：【染色】+【旋转】
				//先写LR后写LL是因为，如果满足LR的条件就能够先直接变成LL再进行LL，不满足就直接进行LL
				//LR
				if (z == p->r)
				{
				//【旋转】
					root = left_rotation(root, p);
					RBTNode* t = z;
					z = p;
					p = z;
				}
				//LL
				//【染色】
				p->color = BLACK;
				g->color = RED;
				//【旋转】
				root = right_rotation(root, g);
			}

		}
	}

}
//插入一个 红黑树节点
RBTree insertRBT(RBTree root, int key)
{
	if (root == NULL)
	{//树空，插入根节点
		root = createNode(key, NULL, NULL, NULL);
		root->color = BLACK;
		return root;
	}
	//树非空，执行BST插入操作
	RBTNode* x = root;//便历找key的位置插入
	RBTNode* xp = NULL;//x的父亲
	while (x != NULL)
	{
		xp = x;
		if (key < x->data)//左找
			x = x->l;
		else//右找
			x = x->r;
	}
	//找到，准备插入
	RBTNode* s = createNode(key, xp, NULL, NULL);
	if (key < xp->data)//左插入
		xp->l = s;
	else//右插入
		xp->r = s;
	//已插入，看是否要调整
	root = fixUp(root, s);
	return root;
}
//中序遍历
void inOrder(RBTNode* root)//为什么是传Node节点过来
{
	if (root != NULL)
	{
		inOrder(root->l);
		printf("%d %d", root->data, root->color);
		if (root->parent != NULL)
			printf("%d\n", root->parent->data);
		else
			printf("-1\n");
		inOrder(root->r);
	}
}
int main()
{
	//输入n个节点，存至数组
	int n = 0;
	int a[104];
	scanf("%d", &n);
	//录入数据：录入到数组
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	//创建根节点
	RBTree root = NULL;
	//将节点插入树中//insertRBT()
	for (int i = 0; i < n; i++)
	{//因为插入会改变结构，所以要带返回值
		root = insertRBT(root, a[i]);
	}
	//中序遍历 检查代码对错//inorder();
	void inOrder(root);
	return 0;
}